package com.heima.algorithm.binarysearch;

public class BinarySearch {
    /**
     * <h3>二分查找基础版</h3>
     *
     * <ol>
     *     <li>i, j, m 指针都可能是查找目标</li>
     *     <li>因为 1. i > j 时表示区域内没有要找的了</li>
     *     <li>每次改变 i, j 边界时, m 已经比较过不是目标, 因此分别 m+1 m-1</li>
     *     <li>向左查找, 比较次数少, 向右查找, 比较次数多</li>
     * </ol>
     *
     * @param array      待查找的升序数组
     * @param target 待查找的目标值
     * @return <p>找到则返回索引</p>
     * <p>找不到返回 -1</p>
     */
    /**
     *
     * 初始版本一
     * @param array
     * @param target
     * @return
     */
//    public static int binarySearchBasic(int[] array,int target){
//    int indexBegin = 0;
//    int indexEnd = array.length -1;
//    while (indexBegin <= indexEnd){//一定是小于等于
//        int median = (indexBegin+indexEnd)/2;//相加可能对于类型溢出
//        if (array[median] < target){
//            indexBegin = median+1;
//        } else if (array[median] >target) {
//            indexEnd = median-1;
//        }else {
//            return median;
//        }
//    }
//    return -1;
//}

    /**
     * 初始版本2
     * 左闭右闭
     */

    public static int binarySearchBasic(int[] array, int target) {
        int indexBegin = 0;
        int indexEnd = array.length - 1;
        while (indexBegin <= indexEnd) {//一定是小于等于
            int median = (indexBegin + indexEnd) >>> 1;//相加可能对于类型溢出
            if (array[median] < target) {//注意小于号细节，直接根据代码看出target在右边
                indexBegin = median + 1;
            } else if (target < array[median]) {//注意小于号细节，直接根据代码看出target在左边
                indexEnd = median - 1;
            } else {
                return median;
            }
        }
        return -1;
    }
    /*
        1 [2,3,4,5] 5  右侧没找到更差
        int i = 0, j = a.length - 1;    2
        return -1;                      1
        元素个数                循环次数
        4-7                    3        floor(log_2(4)) = 2+1
        8-15                   4        floor(log_2(8)) = 3+1
        16-31                  5        floor(log_2(16)) = 4+1
        32-63                  6        floor(log_2(32)) = 5+1
        ...                    ...

        循环次数L  = floor(log_2(n)) + 1

        i <= j                   L+1
        int m = (i + j) >>> 1;   L
        target < a[m]            L
        a[m] < target            L
        i = m + 1;               L

        (floor(log_2(n)) + 1) * 5 + 4

        (3) * 5 + 4 = 19*t
        (10 + 1) * 5 + 4 = 59*t
     */

    /*
        问题1: 为什么是 i<=j 意味着区间内有未比较的元素, 而不是 i<j ?
           i==j 意味着 i,j 它们指向的元素也会参与比较
           i<j 只意味着 m 指向的元素参与比较
        问题2: (i + j) / 2 有没有问题?
        问题3: 都写成小于号有啥好处?
     */

    /**
     * <h3>二分查找改动版</h3>
     *
     * <ol>
     *     <li>i, m 指针可能是查找目标</li>
     *     <li>j 指针不可能是查找目标</li>
     *     <li>因为 1. 2. i >= j 时表示区域内没有要找的了</li>
     *     <li>改变 i 边界时, m 已经比较过不是目标, 因此需要 i=m+1</li>
     *     <li>改变 j 边界时, m 已经比较过不是目标, 同时因为 2. 所以 j=m</li>
     * </ol>
     *
     * @param array  待查找的升序数组
     * @param target 待查找的目标值
     * @return <p>找到则返回索引</p>
     * <p>找不到返回 -1</p>
     */
    public static int binarySearchAlternative(int[] array, int target) {
        int indexBegin = 0;
        int indexEnd = array.length;//在边界外，左闭右开
        while (indexBegin < indexEnd) {//加上等于号会出现死循环
            int median = (indexBegin + indexEnd) >>> 1;
            if (array[median] < target) {
                indexBegin = median + 1;
            } else if (target < array[median]) {
                indexEnd = median;
            } else {
                return median;
            }
        }
        return -1;
    }

    /**
     * <h3>二分查找平衡版</h3>
     *
     * <ol>
     *     <li>不奢望循环内通过 m 找出目标, 缩小区间直至剩 1 个, 剩下的这个可能就是要找的(通过 i)</li>
     *     <li>i 指针可能是查找目标</li>
     *     <li>j 指针不可能是查找目标</li>
     *     <li>因为 1. 2. 3. 当区域内还剩一个元素时, 表示为 j - i == 1</li>
     *     <li>改变 i 边界时, m 可能就是目标, 同时因为 2. 所以有 i=m</li>
     *     <li>改变 j 边界时, m 已经比较过不是目标, 同时因为 3. 所以有 j=m</li>
     *     <li>三分支改为二分支, 循环内比较次数减少</li>
     * </ol>
     *
     * @param array  待查找的升序数组
     * @param target 待查找的目标值
     * @return <p>找到则返回索引</p>
     * <p>找不到返回 -1</p>
     */
    public static int binarySearchBalance(int[] array, int target) {
        int indexBegin = 0;
        int indexEnd = array.length;
        while (1 < indexEnd - indexBegin) {
            int median = (indexBegin + indexEnd) >>> 1;
            if (target < array[median]) {
                indexEnd = median;
            } else {
                indexBegin = median;
            }
        }
        if (array[indexBegin] == target) {
            return indexBegin;
        }
        return -1;
    }


    /**
     * <h3>二分查找 Leftmost </h3>
     *
     * @param array  待查找的升序数组
     * @param target 待查找的目标值
     * @return <p>找到则返回最靠左索引</p>
     * <p>找不到返回 -1</p>
     */
    public static int binarySearchLeftmost1(int[] array, int target) {
        int indexBegin = 0;
        int indexEnd = array.length - 1;
        int candidate = -1;
        while (indexBegin <= indexEnd) {//一定是小于等于
            int median = (indexBegin + indexEnd) >>> 1;//相加可能对于类型溢出
            if (array[median] < target) {//注意小于号细节，直接根据代码看出target在右边
                indexBegin = median + 1;
            } else if (target < array[median]) {//注意小于号细节，直接根据代码看出target在左边
                indexEnd = median - 1;
            } else {
                candidate = median;
                indexEnd = median - 1;
            }
        }
        return candidate;
    }


    /**
     * <h3>二分查找 Rightmost </h3>
     *
     * @param array  待查找的升序数组
     * @param target 待查找的目标值
     * @return <p>找到则返回最靠右索引</p>
     * <p>找不到返回 -1</p>
     */
    public static int binarySearchRightmost1(int[] array, int target) {
        int indexBegin = 0;
        int indexEnd = array.length - 1;
        int candidate = -1;
        while (indexBegin <= indexEnd) {//一定是小于等于
            int median = (indexBegin + indexEnd) >>> 1;//相加可能对于类型溢出
            if (array[median] < target) {//注意小于号细节，直接根据代码看出target在右边
                indexBegin = median + 1;
            } else if (target < array[median]) {//注意小于号细节，直接根据代码看出target在左边
                indexEnd = median - 1;
            } else {
                candidate = median;
                indexBegin = median + 1;
            }
        }
        return candidate;
    }

    /**
     * <h3>二分查找 Leftmost </h3>
     *
     * @param array      待查找的升序数组
     * @param target 待查找的目标值
     * @return <p>返回 大于等于 target 的最靠左索引</p>
     */
    public static int binarySearchLeftmost2(int[] array, int target) {
        int indexBegin = 0;
        int indexEnd = array.length - 1;
        while (indexBegin <= indexEnd) {//一定是小于等于
            int median = (indexBegin + indexEnd) >>> 1;//相加可能对于类型溢出
            if (array[median] < target) {//注意小于号细节，直接根据代码看出target在右边
                indexBegin = median + 1;
            } else if (target <= array[median]) {//注意小于号细节，直接根据代码看出target在左边
                indexEnd = median - 1;
            }
        }
        return indexBegin;
    }

    /**
     * <h3>二分查找 Rightmost </h3>
     *
     * @param array      待查找的升序数组
     * @param target 待查找的目标值
     * @return <p>返回 小于等于 target 的最靠右索引</p>
     */
    public static int binarySearchRightmost2(int[] array, int target) {
        int indexBegin = 0;
        int indexEnd = array.length - 1;
        while (indexBegin <= indexEnd) {//一定是小于等于
            int median = (indexBegin + indexEnd) >>> 1;//相加可能对于类型溢出
            if (array[median] <= target) {//注意小于号细节，直接根据代码看出target在右边
                indexBegin = median + 1;
            } else if (target < array[median]) {//注意小于号细节，直接根据代码看出target在左边
                indexEnd = median - 1;
            }
        }
        return indexEnd;
    }
}
